package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 *
 * 示例 1: 输入: 2 输出: 1
 *
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 *
 * 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于 58。
 */
// 动态规划
public class IntegerBreak {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            // dp[i]为正整数i拆分结果的最大乘积
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i <= n; i ++) {
//                for (int j = 1; j < i; j ++) {
                for (int j = 1; j < i - 1; j ++) {   // 这里 j < i - 1 相当于做了剪枝处理，因为 i - 1 与 1 的和正好为 i ,这样可以少一次循环，使算法效率更高
                    // j * (i - j) 表示将 i 分为 j 和 i - j 两个数相乘
                    // j * dp[i - j] 表示将 i 拆分为 j 和 i - j 之后再将 i - j 继续拆分，取 i -j 拆分之后的乘积的最大值和 j 相乘
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                }
            }
            System.out.println(dp[n]);
        }
    }

}
